#include <vector>

using namespace std;


/**
 * @brief 57. 插入区间
 * https://leetcode.cn/problems/insert-interval/
 */
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        bool inserted = false;
        vector<vector<int>> allIntervals;
        for (auto& interval : intervals) {
            if (!inserted && interval[0] >= newInterval[0]) {
                allIntervals.emplace_back(newInterval);
                inserted = true;
            }
            allIntervals.emplace_back(interval);
        }
        if (!inserted) allIntervals.emplace_back(newInterval);
        
        vector<int> curr;
        vector<vector<int>> res;
        for (auto& interval : allIntervals) {
            if (curr.size() == 0) {
                curr = interval;
            } else if (interval[0] <= curr[1]) {
                curr[1] = max(curr[1], interval[1]);
            } else {
                res.emplace_back(curr);
                curr = interval;
            }
        }
        if (curr.size() != 0) {
            res.emplace_back(curr);
        }

        return res;
    }
};
